#pragma once

#include <set>
#include <vector>
#include <iostream>

using namespace std;

// Grafo implementado na forma de uma estrutura de adjacência
template<typename V = char, typename E = char>
class AltAdjacenceStructGraph
{
  struct Edge
  {
    int node; 
    E value;
  };

  struct CompareEdge
  {
    bool operator()(const Edge &e1, const Edge &e2) const
    {
      return e1.node < e2.node;      
    }
  };  

  typedef set<Edge, CompareEdge> Adjacences;

  struct Node
  {
    V value;
    Adjacences adjacences;
  };

  vector<Node> _nodes;

  void insertEdjeOnNode(int origNode, int dstNode, const E &value)
  {
    Node &n = _nodes[origNode];
    Edge edje {dstNode,value};
    n.adjacences.insert(edje);
  }

  int getNodeDegree(const Node &node) const
  {
    return node.adjacences.size();
  }

public:
  int addNode(const V &value = V())
  {
    _nodes.push_back({value,{}});
    return _nodes.size() - 1;
  }

  const V &getNodeValue(int n) const
  {
    return _nodes[n].value;
  }

  int countNodes() const
  {
    return _nodes.size();
  }

  int getNodeDegree(int node) const
  {
    return _nodes[node].adjacences.size();
  }

  int countEdges() const
  {
    int count = 0;

    for (const Node &node: _nodes) {
      count += getNodeDegree(node);
    }

    return count/2;
  }

  bool isAValidNode(int node) const
  {
    int lastIndex = _nodes.size() - 1;
    return node <= lastIndex;
  }
  
  bool addEdge(int node1, int node2, const E &value = E())
  {
    int lastIndex = _nodes.size() - 1;

    // não posso ter loops nem tentar adicionar arestas entre nós que não existem
    if (!isAValidNode(node1) || !isAValidNode(node2) || node1 == node2) {
      return false;
    }

    insertEdjeOnNode(node1, node2, value);

    insertEdjeOnNode(node2, node1, value);

    return true;
  }
  
  bool areNodesAdjacents(int node1, int node2)
  {
    // FIXME: cópia do código de addEdge!
    // não posso ter loops nem tentar adicionar arestas entre nós que não existem
    if (!isAValidNode(node1) || !isAValidNode(node2) || node1 == node2) {
      return false;
    }
    
    // node2 está na adjacencesa de adjacência de node1?
    return _nodes[node1].adjacences.find({node2,E()}) != _nodes[node1].adjacences.end();
  }
  
  const E &getEdgeValue(int node1, int node2) const
  {
    return _nodes[node1].adjacences.find({node2,E()})->value;
  }

  vector<int> getAdjacentNodes(int node) const
  {
    vector<int> r;
    for (auto edge: _nodes[node].adjacences) {
      r.push_back(edge.node);
    }
    return r;
  }
};
